home *** CD-ROM | disk | FTP | other *** search
- /* Copyright (C) 1989, 1995, 1996, 1998, 1999 Aladdin Enterprises. All rights reserved.
-
- This file is part of AFPL Ghostscript.
-
- AFPL Ghostscript is distributed with NO WARRANTY OF ANY KIND. No author or
- distributor accepts any responsibility for the consequences of using it, or
- for whether it serves any particular purpose or works at all, unless he or
- she says so in writing. Refer to the Aladdin Free Public License (the
- "License") for full details.
-
- Every copy of AFPL Ghostscript must include a copy of the License, normally
- in a plain ASCII text file named PUBLIC. The License grants you the right
- to copy, modify and redistribute AFPL Ghostscript, but only under certain
- conditions described in the License. Among other things, the License
- requires that the copyright notice and this notice be preserved on all
- copies.
- */
-
- /*$Id: gsmatrix.c,v 1.2 2000/09/19 19:00:29 lpd Exp $ */
- /* Matrix operators for Ghostscript library */
- #include "math_.h"
- #include "memory_.h"
- #include "gx.h"
- #include "gserrors.h"
- #include "gxfarith.h"
- #include "gxfixed.h"
- #include "gxmatrix.h"
- #include "stream.h"
-
- /* The identity matrix */
- private const gs_matrix gs_identity_matrix =
- {identity_matrix_body};
-
- /* ------ Matrix creation ------ */
-
- /* Create an identity matrix */
- void
- gs_make_identity(gs_matrix * pmat)
- {
- *pmat = gs_identity_matrix;
- }
-
- /* Create a translation matrix */
- int
- gs_make_translation(floatp dx, floatp dy, gs_matrix * pmat)
- {
- *pmat = gs_identity_matrix;
- pmat->tx = dx;
- pmat->ty = dy;
- return 0;
- }
-
- /* Create a scaling matrix */
- int
- gs_make_scaling(floatp sx, floatp sy, gs_matrix * pmat)
- {
- *pmat = gs_identity_matrix;
- pmat->xx = sx;
- pmat->yy = sy;
- return 0;
- }
-
- /* Create a rotation matrix. */
- /* The angle is in degrees. */
- int
- gs_make_rotation(floatp ang, gs_matrix * pmat)
- {
- gs_sincos_t sincos;
-
- gs_sincos_degrees(ang, &sincos);
- pmat->yy = pmat->xx = sincos.cos;
- pmat->xy = sincos.sin;
- pmat->yx = -sincos.sin;
- pmat->tx = pmat->ty = 0.0;
- return 0;
- }
-
- /* ------ Matrix arithmetic ------ */
-
- /* Multiply two matrices. We should check for floating exceptions, */
- /* but for the moment it's just too awkward. */
- /* Since this is used heavily, we check for shortcuts. */
- int
- gs_matrix_multiply(const gs_matrix * pm1, const gs_matrix * pm2, gs_matrix * pmr)
- {
- double xx1 = pm1->xx, yy1 = pm1->yy;
- double tx1 = pm1->tx, ty1 = pm1->ty;
- double xx2 = pm2->xx, yy2 = pm2->yy;
- double xy2 = pm2->xy, yx2 = pm2->yx;
-
- if (is_xxyy(pm1)) {
- pmr->tx = tx1 * xx2 + pm2->tx;
- pmr->ty = ty1 * yy2 + pm2->ty;
- if (is_fzero(xy2))
- pmr->xy = 0;
- else
- pmr->xy = xx1 * xy2,
- pmr->ty += tx1 * xy2;
- pmr->xx = xx1 * xx2;
- if (is_fzero(yx2))
- pmr->yx = 0;
- else
- pmr->yx = yy1 * yx2,
- pmr->tx += ty1 * yx2;
- pmr->yy = yy1 * yy2;
- } else {
- double xy1 = pm1->xy, yx1 = pm1->yx;
-
- pmr->xx = xx1 * xx2 + xy1 * yx2;
- pmr->xy = xx1 * xy2 + xy1 * yy2;
- pmr->yy = yx1 * xy2 + yy1 * yy2;
- pmr->yx = yx1 * xx2 + yy1 * yx2;
- pmr->tx = tx1 * xx2 + ty1 * yx2 + pm2->tx;
- pmr->ty = tx1 * xy2 + ty1 * yy2 + pm2->ty;
- }
- return 0;
- }
-
- /* Invert a matrix. Return gs_error_undefinedresult if not invertible. */
- int
- gs_matrix_invert(const gs_matrix * pm, gs_matrix * pmr)
- { /* We have to be careful about fetch/store order, */
- /* because pm might be the same as pmr. */
- if (is_xxyy(pm)) {
- if (is_fzero(pm->xx) || is_fzero(pm->yy))
- return_error(gs_error_undefinedresult);
- pmr->tx = -(pmr->xx = 1.0 / pm->xx) * pm->tx;
- pmr->xy = 0.0;
- pmr->yx = 0.0;
- pmr->ty = -(pmr->yy = 1.0 / pm->yy) * pm->ty;
- } else {
- double det = pm->xx * pm->yy - pm->xy * pm->yx;
- double mxx = pm->xx, mtx = pm->tx;
-
- if (det == 0)
- return_error(gs_error_undefinedresult);
- pmr->xx = pm->yy / det;
- pmr->xy = -pm->xy / det;
- pmr->yx = -pm->yx / det;
- pmr->yy = mxx / det; /* xx is already changed */
- pmr->tx = -(mtx * pmr->xx + pm->ty * pmr->yx);
- pmr->ty = -(mtx * pmr->xy + pm->ty * pmr->yy); /* tx ditto */
- }
- return 0;
- }
-
- /* Translate a matrix, possibly in place. */
- int
- gs_matrix_translate(const gs_matrix * pm, floatp dx, floatp dy, gs_matrix * pmr)
- {
- gs_point trans;
- int code = gs_distance_transform(dx, dy, pm, &trans);
-
- if (code < 0)
- return code;
- if (pmr != pm)
- *pmr = *pm;
- pmr->tx += trans.x;
- pmr->ty += trans.y;
- return 0;
- }
-
- /* Scale a matrix, possibly in place. */
- int
- gs_matrix_scale(const gs_matrix * pm, floatp sx, floatp sy, gs_matrix * pmr)
- {
- pmr->xx = pm->xx * sx;
- pmr->xy = pm->xy * sx;
- pmr->yx = pm->yx * sy;
- pmr->yy = pm->yy * sy;
- if (pmr != pm) {
- pmr->tx = pm->tx;
- pmr->ty = pm->ty;
- }
- return 0;
- }
-
- /* Rotate a matrix, possibly in place. The angle is in degrees. */
- int
- gs_matrix_rotate(const gs_matrix * pm, floatp ang, gs_matrix * pmr)
- {
- double mxx, mxy;
- gs_sincos_t sincos;
-
- gs_sincos_degrees(ang, &sincos);
- mxx = pm->xx, mxy = pm->xy;
- pmr->xx = sincos.cos * mxx + sincos.sin * pm->yx;
- pmr->xy = sincos.cos * mxy + sincos.sin * pm->yy;
- pmr->yx = sincos.cos * pm->yx - sincos.sin * mxx;
- pmr->yy = sincos.cos * pm->yy - sincos.sin * mxy;
- if (pmr != pm) {
- pmr->tx = pm->tx;
- pmr->ty = pm->ty;
- }
- return 0;
- }
-
- /* ------ Coordinate transformations (floating point) ------ */
-
- /* Note that all the transformation routines take separate */
- /* x and y arguments, but return their result in a point. */
-
- /* Transform a point. */
- int
- gs_point_transform(floatp x, floatp y, const gs_matrix * pmat,
- gs_point * ppt)
- {
- ppt->x = x * pmat->xx + pmat->tx;
- ppt->y = y * pmat->yy + pmat->ty;
- if (!is_fzero(pmat->yx))
- ppt->x += y * pmat->yx;
- if (!is_fzero(pmat->xy))
- ppt->y += x * pmat->xy;
- return 0;
- }
-
- /* Inverse-transform a point. */
- /* Return gs_error_undefinedresult if the matrix is not invertible. */
- int
- gs_point_transform_inverse(floatp x, floatp y, const gs_matrix * pmat,
- gs_point * ppt)
- {
- if (is_xxyy(pmat)) {
- if (is_fzero(pmat->xx) || is_fzero(pmat->yy))
- return_error(gs_error_undefinedresult);
- ppt->x = (x - pmat->tx) / pmat->xx;
- ppt->y = (y - pmat->ty) / pmat->yy;
- return 0;
- } else if (is_xyyx(pmat)) {
- if (is_fzero(pmat->xy) || is_fzero(pmat->yx))
- return_error(gs_error_undefinedresult);
- ppt->x = (y - pmat->ty) / pmat->xy;
- ppt->y = (x - pmat->tx) / pmat->yx;
- return 0;
- } else { /* There are faster ways to do this, */
- /* but we won't implement one unless we have to. */
- gs_matrix imat;
- int code = gs_matrix_invert(pmat, &imat);
-
- if (code < 0)
- return code;
- return gs_point_transform(x, y, &imat, ppt);
- }
- }
-
- /* Transform a distance. */
- int
- gs_distance_transform(floatp dx, floatp dy, const gs_matrix * pmat,
- gs_point * pdpt)
- {
- pdpt->x = dx * pmat->xx;
- pdpt->y = dy * pmat->yy;
- if (!is_fzero(pmat->yx))
- pdpt->x += dy * pmat->yx;
- if (!is_fzero(pmat->xy))
- pdpt->y += dx * pmat->xy;
- return 0;
- }
-
- /* Inverse-transform a distance. */
- /* Return gs_error_undefinedresult if the matrix is not invertible. */
- int
- gs_distance_transform_inverse(floatp dx, floatp dy,
- const gs_matrix * pmat, gs_point * pdpt)
- {
- if (is_xxyy(pmat)) {
- if (is_fzero(pmat->xx) || is_fzero(pmat->yy))
- return_error(gs_error_undefinedresult);
- pdpt->x = dx / pmat->xx;
- pdpt->y = dy / pmat->yy;
- } else if (is_xyyx(pmat)) {
- if (is_fzero(pmat->xy) || is_fzero(pmat->yx))
- return_error(gs_error_undefinedresult);
- pdpt->x = dy / pmat->xy;
- pdpt->y = dx / pmat->yx;
- } else {
- double det = pmat->xx * pmat->yy - pmat->xy * pmat->yx;
-
- if (det == 0)
- return_error(gs_error_undefinedresult);
- pdpt->x = (dx * pmat->yy - dy * pmat->yx) / det;
- pdpt->y = (dy * pmat->xx - dx * pmat->xy) / det;
- }
- return 0;
- }
-
- /* Compute the bounding box of 4 points. */
- int
- gs_points_bbox(const gs_point pts[4], gs_rect * pbox)
- {
- #define assign_min_max(vmin, vmax, v0, v1)\
- if ( v0 < v1 ) vmin = v0, vmax = v1; else vmin = v1, vmax = v0
- #define assign_min_max_4(vmin, vmax, v0, v1, v2, v3)\
- { double min01, max01, min23, max23;\
- assign_min_max(min01, max01, v0, v1);\
- assign_min_max(min23, max23, v2, v3);\
- vmin = min(min01, min23);\
- vmax = max(max01, max23);\
- }
- assign_min_max_4(pbox->p.x, pbox->q.x,
- pts[0].x, pts[1].x, pts[2].x, pts[3].x);
- assign_min_max_4(pbox->p.y, pbox->q.y,
- pts[0].y, pts[1].y, pts[2].y, pts[3].y);
- #undef assign_min_max
- #undef assign_min_max_4
- return 0;
- }
-
- /* Transform or inverse-transform a bounding box. */
- /* Return gs_error_undefinedresult if the matrix is not invertible. */
- private int
- bbox_transform_either_only(const gs_rect * pbox_in, const gs_matrix * pmat,
- gs_point pts[4],
- int (*point_xform) (P4(floatp, floatp, const gs_matrix *, gs_point *)))
- {
- int code;
-
- if ((code = (*point_xform) (pbox_in->p.x, pbox_in->p.y, pmat, &pts[0])) < 0 ||
- (code = (*point_xform) (pbox_in->p.x, pbox_in->q.y, pmat, &pts[1])) < 0 ||
- (code = (*point_xform) (pbox_in->q.x, pbox_in->p.y, pmat, &pts[2])) < 0 ||
- (code = (*point_xform) (pbox_in->q.x, pbox_in->q.y, pmat, &pts[3])) < 0
- )
- DO_NOTHING;
- return code;
- }
-
- private int
- bbox_transform_either(const gs_rect * pbox_in, const gs_matrix * pmat,
- gs_rect * pbox_out,
- int (*point_xform) (P4(floatp, floatp, const gs_matrix *, gs_point *)))
- {
- int code;
-
- /*
- * In principle, we could transform only one point and two
- * distance vectors; however, because of rounding, we will only
- * get fully consistent results if we transform all 4 points.
- * We must compute the max and min after transforming,
- * since a rotation may be involved.
- */
- gs_point pts[4];
-
- if ((code = bbox_transform_either_only(pbox_in, pmat, pts, point_xform)) < 0)
- return code;
- return gs_points_bbox(pts, pbox_out);
- }
- int
- gs_bbox_transform(const gs_rect * pbox_in, const gs_matrix * pmat,
- gs_rect * pbox_out)
- {
- return bbox_transform_either(pbox_in, pmat, pbox_out,
- gs_point_transform);
- }
- int
- gs_bbox_transform_only(const gs_rect * pbox_in, const gs_matrix * pmat,
- gs_point points[4])
- {
- return bbox_transform_either_only(pbox_in, pmat, points,
- gs_point_transform);
- }
- int
- gs_bbox_transform_inverse(const gs_rect * pbox_in, const gs_matrix * pmat,
- gs_rect * pbox_out)
- {
- return bbox_transform_either(pbox_in, pmat, pbox_out,
- gs_point_transform_inverse);
- }
-
- /* ------ Coordinate transformations (to fixed point) ------ */
-
- #define f_fits_in_fixed(f) f_fits_in_bits(f, fixed_int_bits)
-
- /* Make a gs_matrix_fixed from a gs_matrix. */
- int
- gs_matrix_fixed_from_matrix(gs_matrix_fixed *pfmat, const gs_matrix *pmat)
- {
- *(gs_matrix *)pfmat = *pmat;
- if (f_fits_in_fixed(pmat->tx) && f_fits_in_fixed(pmat->ty)) {
- pfmat->tx = fixed2float(pfmat->tx_fixed = float2fixed(pmat->tx));
- pfmat->ty = fixed2float(pfmat->ty_fixed = float2fixed(pmat->ty));
- pfmat->txy_fixed_valid = true;
- } else {
- pfmat->txy_fixed_valid = false;
- }
- return 0;
- }
-
- /* Transform a point with a fixed-point result. */
- int
- gs_point_transform2fixed(const gs_matrix_fixed * pmat,
- floatp x, floatp y, gs_fixed_point * ppt)
- {
- fixed px, py, t;
- double xtemp, ytemp;
- int code;
-
- if (!pmat->txy_fixed_valid) { /* The translation is out of range. Do the */
- /* computation in floating point, and convert to */
- /* fixed at the end. */
- gs_point fpt;
-
- gs_point_transform(x, y, (const gs_matrix *)pmat, &fpt);
- if (!(f_fits_in_fixed(fpt.x) && f_fits_in_fixed(fpt.y)))
- return_error(gs_error_limitcheck);
- ppt->x = float2fixed(fpt.x);
- ppt->y = float2fixed(fpt.y);
- return 0;
- }
- if (!is_fzero(pmat->xy)) { /* Hope for 90 degree rotation */
- if ((code = CHECK_DFMUL2FIXED_VARS(px, y, pmat->yx, xtemp)) < 0 ||
- (code = CHECK_DFMUL2FIXED_VARS(py, x, pmat->xy, ytemp)) < 0
- )
- return code;
- FINISH_DFMUL2FIXED_VARS(px, xtemp);
- FINISH_DFMUL2FIXED_VARS(py, ytemp);
- if (!is_fzero(pmat->xx)) {
- if ((code = CHECK_DFMUL2FIXED_VARS(t, x, pmat->xx, xtemp)) < 0)
- return code;
- FINISH_DFMUL2FIXED_VARS(t, xtemp);
- px += t; /* should check for overflow */
- }
- if (!is_fzero(pmat->yy)) {
- if ((code = CHECK_DFMUL2FIXED_VARS(t, y, pmat->yy, ytemp)) < 0)
- return code;
- FINISH_DFMUL2FIXED_VARS(t, ytemp);
- py += t; /* should check for overflow */
- }
- } else {
- if ((code = CHECK_DFMUL2FIXED_VARS(px, x, pmat->xx, xtemp)) < 0 ||
- (code = CHECK_DFMUL2FIXED_VARS(py, y, pmat->yy, ytemp)) < 0
- )
- return code;
- FINISH_DFMUL2FIXED_VARS(px, xtemp);
- FINISH_DFMUL2FIXED_VARS(py, ytemp);
- if (!is_fzero(pmat->yx)) {
- if ((code = CHECK_DFMUL2FIXED_VARS(t, y, pmat->yx, ytemp)) < 0)
- return code;
- FINISH_DFMUL2FIXED_VARS(t, ytemp);
- px += t; /* should check for overflow */
- }
- }
- ppt->x = px + pmat->tx_fixed; /* should check for overflow */
- ppt->y = py + pmat->ty_fixed; /* should check for overflow */
- return 0;
- }
-
- /* Transform a distance with a fixed-point result. */
- int
- gs_distance_transform2fixed(const gs_matrix_fixed * pmat,
- floatp dx, floatp dy, gs_fixed_point * ppt)
- {
- fixed px, py, t;
- double xtemp, ytemp;
- int code;
-
- if ((code = CHECK_DFMUL2FIXED_VARS(px, dx, pmat->xx, xtemp)) < 0 ||
- (code = CHECK_DFMUL2FIXED_VARS(py, dy, pmat->yy, ytemp)) < 0
- )
- return code;
- FINISH_DFMUL2FIXED_VARS(px, xtemp);
- FINISH_DFMUL2FIXED_VARS(py, ytemp);
- if (!is_fzero(pmat->yx)) {
- if ((code = CHECK_DFMUL2FIXED_VARS(t, dy, pmat->yx, ytemp)) < 0)
- return code;
- FINISH_DFMUL2FIXED_VARS(t, ytemp);
- px += t; /* should check for overflow */
- }
- if (!is_fzero(pmat->xy)) {
- if ((code = CHECK_DFMUL2FIXED_VARS(t, dx, pmat->xy, xtemp)) < 0)
- return code;
- FINISH_DFMUL2FIXED_VARS(t, xtemp);
- py += t; /* should check for overflow */
- }
- ppt->x = px;
- ppt->y = py;
- return 0;
- }
-
- /* ------ Serialization ------ */
-
- /*
- * For maximum conciseness in band lists, we write a matrix as a control
- * byte followed by 0 to 6 values. The control byte has the format
- * AABBCD00. AA and BB control (xx,yy) and (xy,yx) as follows:
- * 00 = values are (0.0, 0.0)
- * 01 = values are (V, V) [1 value follows]
- * 10 = values are (V, -V) [1 value follows]
- * 11 = values are (U, V) [2 values follow]
- * C and D control tx and ty as follows:
- * 0 = value is 0.0
- * 1 = value follows
- * The following code is the only place that knows this representation.
- */
-
- /* Put a matrix on a stream. */
- int
- sput_matrix(stream *s, const gs_matrix *pmat)
- {
- byte buf[1 + 6 * sizeof(float)];
- byte *cp = buf + 1;
- byte b = 0;
- float coeff[6];
- int i;
- uint ignore;
-
- coeff[0] = pmat->xx;
- coeff[1] = pmat->xy;
- coeff[2] = pmat->yx;
- coeff[3] = pmat->yy;
- coeff[4] = pmat->tx;
- coeff[5] = pmat->ty;
- for (i = 0; i < 4; i += 2) {
- float u = coeff[i], v = coeff[i ^ 3];
-
- b <<= 2;
- if (u != 0 || v != 0) {
- memcpy(cp, &u, sizeof(float));
- cp += sizeof(float);
-
- if (v == u)
- b += 1;
- else if (v == -u)
- b += 2;
- else {
- b += 3;
- memcpy(cp, &v, sizeof(float));
- cp += sizeof(float);
- }
- }
- }
- for (; i < 6; ++i) {
- float v = coeff[i];
-
- b <<= 1;
- if (v != 0) {
- ++b;
- memcpy(cp, &v, sizeof(float));
- cp += sizeof(float);
- }
- }
- buf[0] = b << 2;
- return sputs(s, buf, cp - buf, &ignore);
- }
-
- /* Get a matrix from a stream. */
- int
- sget_matrix(stream *s, gs_matrix *pmat)
- {
- int b = sgetc(s);
- float coeff[6];
- int i;
- int status;
- uint nread;
-
- if (b < 0)
- return b;
- for (i = 0; i < 4; i += 2, b <<= 2)
- if (!(b & 0xc0))
- coeff[i] = coeff[i ^ 3] = 0.0;
- else {
- float value;
-
- status = sgets(s, (byte *)&value, sizeof(value), &nread);
- if (status < 0)
- return status;
- coeff[i] = value;
- switch ((b >> 6) & 3) {
- case 1:
- coeff[i ^ 3] = value;
- break;
- case 2:
- coeff[i ^ 3] = -value;
- break;
- case 3:
- status = sgets(s, (byte *)&coeff[i ^ 3],
- sizeof(coeff[0]), &nread);
- if (status < 0)
- return status;
- }
- }
- for (; i < 6; ++i, b <<= 1)
- if (b & 0x80) {
- status = sgets(s, (byte *)&coeff[i], sizeof(coeff[0]), &nread);
- if (status < 0)
- return status;
- } else
- coeff[i] = 0.0;
- pmat->xx = coeff[0];
- pmat->xy = coeff[1];
- pmat->yx = coeff[2];
- pmat->yy = coeff[3];
- pmat->tx = coeff[4];
- pmat->ty = coeff[5];
- return 0;
- }
-